/**************************************************************************************************
	$Header: /pub/cvsroot/mydns/src/mydns/cache.c,v 1.24 2002/08/31 08:08:00 bboy Exp $
	cache.c: Routines to implement a cache.

	Copyright (C) 2002  Don Moore <bboy@bboy.net>

	This program is free software; you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation; either version 2 of the License, or
	(at Your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program; if not, write to the Free Software
	Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
**************************************************************************************************/

#include "named.h"

CACHE *Cache = NULL;									/* Our cache */


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	ISPRIME
	Returns 1 if `number' is a prime number, 0 if not.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
static int
isprime(u_int number)
{
	register u_int div = 3;

	while (div * div < number && number % div != 0)
		div += 2;
	return (number % div != 0);
}
/*--- isprime() ---------------------------------------------------------------------------------*/


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	CACHE_INIT
	Create and return a new CACHE structure.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void
cache_init(void)
{
	u_int32_t limit = atou(conf_get(&Conf, "cache-size"));
	int expire = atou(conf_get(&Conf, "cache-expire"));

	/* A cache size of zero means no cache */
	if (!limit || !expire)
		return;

	Cache = xcalloc(1, sizeof(CACHE));
	Cache->limit = limit;
	Cache->expire = expire;

#if (HASH_TYPE == ORIGINAL_HASH) || (HASH_TYPE == ADDITIVE_HASH)
	/* Make `slots' prime */
	Cache->slots = limit * CACHE_SLOT_MULTIPLIER;
	Cache->slots |= 1;
	while (!isprime(Cache->slots))
		Cache->slots += 2;
#if DEBUG && (HASH_TYPE == ORIGINAL_HASH)
	Debug(_("%s: %s (%d)"), _("hash type"), _("original"), (int)HASH_TYPE);
#endif
#if DEBUG && (HASH_TYPE == ADDITIVE_HASH)
	Debug(_("%s: %s (%d)"), _("hash type"), _("additive"), (int)HASH_TYPE);
#endif
#elif (HASH_TYPE == ROTATING_HASH)
	/* Make `slots' a power of two */
	{
		int bits;
		u_int32_t slots;

		Cache->slots = limit * CACHE_SLOT_MULTIPLIER;
		for (slots = Cache->slots, bits = 0; slots != 1; )
		{
			slots >>= 1;
			bits++;
		}
		if (Cache->slots & ((1 << bits) - 1))
			bits++;
		slots = 1 << bits;

   	Cache->slots = slots;
		Cache->mask = Cache->slots - 1;
#if DEBUG
		Debug(_("%s: %s (%d)"), _("hash type"), _("rotating"), (int)HASH_TYPE);
#endif
	}
#else
#	error Hash method unknown or unspecified
#endif

	Cache->nodes = xcalloc(Cache->slots, sizeof(CNODE *));

#if DEBUG
	Debug(_("cache initialized (%u nodes, %u elements max)"), Cache->slots, limit);
#endif
}
/*--- cache_init() ------------------------------------------------------------------------------*/


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	CACHE_STATUS
	Called when SIGUSR1 is received, returns a string to append to status.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
char *
cache_status(void)
{
	static char str[256];
	size_t cache_size = 0;
	register int ct;
	register CNODE *n;

	if (!Cache)
		return _("no cache");

	/* Get the total amount of memory used by the cache */
	cache_size += sizeof(CACHE);
	cache_size += (sizeof(CNODE *) * Cache->slots);
	for (ct = 0; ct < (Cache->slots); ct++)
		for (n = Cache->nodes[ct]; n; n = n->next_node)
		{
			cache_size += sizeof(CNODE) + n->namelen + 1;
			if (n->data)
			{
				if (n->type == DNS_T_SOA)
					cache_size += mydns_soa_size((MYDNS_SOA *)n->data);
				else
					cache_size += mydns_rr_size((MYDNS_RR *)n->data);
			}
		}

	snprintf(str, sizeof(str),
		_("cache %.0f%% useful (%u from cache, %u from db), %.0f%% full, %u bytes"),
		PCT(Cache->questions, Cache->hits),
		Cache->hits, Cache->misses,
		PCT(Cache->limit, Cache->count),
		cache_size);

	return (str);
}
/*--- cache_status() ----------------------------------------------------------------------------*/


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	MRULIST_ADD
	Adds the specified node to the head of the MRU list.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
static void
mrulist_add(CNODE *n)
{
	register CNODE *head = Cache->mru_head;

	if (!n || !Cache) return;

	if (!Cache->mru_head)
	{
		Cache->mru_head = n;
		Cache->mru_head->mru_prev = NULL;
		Cache->mru_head->mru_next = NULL;
		Cache->mru_tail = n;
	}
	else
	{
		n->mru_next = head;
		n->mru_prev = head->mru_prev;
		if (head->mru_prev == NULL)
			Cache->mru_head = n;
		else
			head->mru_prev->mru_next = n;
		head->mru_prev = n;
	}
}
/*--- mrulist_add() -----------------------------------------------------------------------------*/


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	MRULIST_DEL
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
static void
mrulist_del(CNODE *n)
{
	if (!n || !Cache || !Cache->mru_head) return;

	if (n == Cache->mru_head)
	{
		Cache->mru_head = n->mru_next;
		if (Cache->mru_head == NULL)
			Cache->mru_tail = NULL;
		else
			n->mru_next->mru_prev = NULL;
	}
	else
	{
		n->mru_prev->mru_next = n->mru_next;
		if (n->mru_next == NULL)
			Cache->mru_tail = n->mru_prev;
		else
			n->mru_next->mru_prev = n->mru_prev;
	}
}
/*--- mrulist_del() -----------------------------------------------------------------------------*/


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	CACHE_FREE_NODE
	Frees the node specified and removes it from the cache.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
static void
cache_free_node(u_int32_t hash, CNODE *n)
{
	register CNODE *prev = NULL, *cur, *next;

	if (!n || hash >= Cache->slots)
		return;

	for (cur = Cache->nodes[hash]; cur; cur = next)
	{
		next = cur->next_node;
		if (cur == n)		/* Delete this node */
		{
			mrulist_del(n);										/* Remove from MRU/LRU list */

			/* Remove the node */
			if (cur->type == DNS_T_SOA)
			{
				mydns_soa_free((MYDNS_SOA *)cur->data);
			}
			else
			{
				mydns_rr_free((MYDNS_RR *)cur->data);
			}
			if (cur == Cache->nodes[hash])					/* Head of node? */
				Cache->nodes[hash] = cur->next_node;
			else if (prev)
				prev->next_node = cur->next_node;
			free(cur);
			Cache->out++;
			Cache->count--;
			return;
		}
		else
			prev = cur;
	}
	Errx(_("tried to free invalid node %p at %u in cache"), n, hash);
}
/*--- cache_free_node() -------------------------------------------------------------------------*/


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	CACHE_EMPTY
	Deletes all nodes within the cache.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void
cache_empty(void)
{
	register int ct;
	register CNODE *n, *tmp;

	if (!Cache) return;
	for (ct = 0; ct < Cache->slots; ct++)
		for (n = Cache->nodes[ct]; n; n = tmp)
		{
			tmp = n->next_node;
			cache_free_node(ct, n);
		}
	Cache->mru_head = Cache->mru_tail = NULL;
}
/*--- cache_empty() -----------------------------------------------------------------------------*/


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	CACHE_CLEANUP
	Deletes all expired nodes within the cache.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void
cache_cleanup(void)
{
	register int ct;
	register CNODE *n, *tmp;

	if (!Cache) return;
	for (ct = 0; ct < Cache->slots; ct++)
		for (n = Cache->nodes[ct]; n; n = tmp)
		{
			tmp = n->next_node;
			if (current_time > n->expire)
			{
				Cache->expired++;
				cache_free_node(ct, n);
			}
		}
#if DEBUG
	Debug("cache cleanup; %s", cache_status());
#endif
}
/*--- cache_cleanup() ---------------------------------------------------------------------------*/


/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	CACHE_FIND
	Returns the SOA from cache (or via MySQL if necessary) or NULL if `name' doesn't match.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void *
cache_find(zone, origin, type, name, namelen)
	u_int32_t zone;
	unsigned char *origin;
	dns_qtype_t type;
	unsigned char *name;
	size_t namelen;
{
	register u_char *p;
	register u_int32_t hash = 0;
	register CNODE *n;
	MYDNS_SOA *soa = NULL;
	MYDNS_RR	 *rr = NULL;

	if (!name) return (NULL);

	if (Cache)
	{
		Cache->questions++;

		/* Generate hash value */
#if (HASH_TYPE == ORIGINAL_HASH)
		for (hash = zone + type, p = name; p < name + namelen; p++)
		{
			register int tmp;
			hash = (hash << 4) + (*p);
			if ((tmp = (hash & 0xf0000000)))
			{
				hash = hash ^ (tmp >> 24);
				hash = hash ^ tmp;
			}
		}
		hash %= Cache->slots;
#elif (HASH_TYPE == ADDITIVE_HASH)
		for (hash = zone + type, p = name; p < name + namelen; p++)
			hash += *p;
		hash %= Cache->slots;
#elif (HASH_TYPE == ROTATING_HASH)
		for (hash = zone + type, p = name; p < name + namelen; p++)
			hash = (hash << 4) ^ (hash >> 28) ^ (*p);
		hash = (hash ^ (hash>>10) ^ (hash>>20)) & Cache->mask;
#else
#	error Hash method unknown or unspecified
#endif

		/* Look at the appropriate node.  Descend list and find match. */
		for (n = Cache->nodes[hash]; n; n = n->next_node)
		{
			if ((n->namelen == namelen)
				 && (n->zone == zone)
				 && (n->type == type))
			{
				if (!n->name)
					Errx(_("cache node %p at hash %u has NULL name"), n, hash);
				if (!memcmp(n->name, name, namelen))
				{
					if (current_time > n->expire)						/* Node expired */
					{
						cache_free_node(hash, n);
						break;
					}
					Cache->hits++;
					/* Found in cache; move to head of usefulness list */
					mrulist_del(n);
					mrulist_add(n);
					if (type == DNS_T_SOA)
						return (n->data ? mydns_soa_dup(n->data, 1) : NULL);
					else
						return (n->data ? mydns_rr_dup(n->data, 1) : NULL);
				}
			}
		}
	}

	/* Result not found in cache; Get answer from database */
	if (type == DNS_T_SOA)
	{
		if (mydns_soa_load(mysql, &soa, name) != 0)
			WarnSQL(mysql, "%s: %s", name, _("error loading SOA"));
		if (!Cache)
			return ((void *)soa);
	}
	else
	{
		if (mydns_rr_load(mysql, &rr, zone, type, name, origin) != 0)
			WarnSQL(mysql, _("error finding %s type resource records for name `%s' in zone %u"),
					  mydns_qtype_str(type), name, zone);
		if (!Cache)
			return ((void *)rr);
	}
	Cache->misses++;

	/* If the cache is full, delete the least recently used node and add new node */
	if (Cache->count >= Cache->limit)
	{
		if (Cache->mru_tail)
		{
			Cache->removed++;
			cache_free_node(Cache->mru_tail->hash, Cache->mru_tail);
		}
		else
			return (type == DNS_T_SOA ? (void *)soa : (void *)rr);
	}

	/* Add to cache */
	Cache->in++;
	if (!(n = calloc(1, sizeof(CNODE))))
		Err("calloc");
	n->hash = hash;
	n->zone = zone;
	n->type = type;
	strncpy(n->name, name, sizeof(n->name)-1);
	n->namelen = namelen;
	if (type == DNS_T_SOA)
		n->data = mydns_soa_dup(soa, 1);
	else
		n->data = mydns_rr_dup(rr, 1);
	n->expire = current_time + Cache->expire;
	n->next_node = Cache->nodes[hash];

	/* Add node to cache */
	Cache->nodes[hash] = n;
	Cache->count++;

	/* Add node to head of MRU list */
	mrulist_add(n);

	return (type == DNS_T_SOA ? (void *)soa : (void *)rr);
}
/*--- cache_find() ------------------------------------------------------------------------------*/

/* vi:set ts=3: */
/* NEED_PO */
